1677C - Tokitsukaze and Two Colorful Tapes - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
int dfs(int x, int p) {
  int ret=1;
  vis[x]=1;
  for(int pp : adj[x]) {
    if(pp==p) continue;
    if(vis[pp]) continue;
    ret+=dfs(pp, x);
  } return ret;
}
int solve() {
  int n; cin >> n; 
  adj.resize(n); vis.resize(n);
  vector<int> a(n);
  for(int &p : a) cin >> p, --p;
  for(int i=0; i<n; i++) {
    int p; cin >> p; --p;
    adj[p].push_back(a[i]);
    adj[a[i]].push_back(p);}
  priority_queue<int> pq;
  for(int i=0; i<n; i++) {
    if(vis[i]) continue;
    int bro=dfs(i, -1);
    if(bro>1) pq.push(bro);}
  int ans=0, i=0, l=1, r=n, par=0, midL=n/2, midR=n/2+1, midPar=0;
  while(!pq.empty()) {
    int sz=pq.top(); pq.pop();
    vector<int> b(sz/2*2);
    for(int &p : b) {
      if(par) p=(l++);
      else p=(r--);
      par^=1;}
    if(sz&1) {
      if(midPar) b.push_back(midL--);
      else b.push_back(midR++);
      midPar^=1;}
    for(int i=1; i<b.size(); i++) ans+=abs(b[i]-b[i-1]);
    ans+=abs(b[b.size()-1]-b[0]);
  }
  adj.clear(); vis.clear();
  return ans;
}
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int _; cin >> _;
  while(_--) cout << solve() << '\n';
  return 0;
}